package com.mapbar.ure.backend.converter;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map;
import java.util.Stack;

import com.mapbar.ure.backend.DFA;
import com.mapbar.ure.backend.DFANode;
import com.mapbar.ure.backend.NFA;
import com.mapbar.ure.backend.NFANode;
import com.mapbar.ure.utils.ChangingMonitorHashSet;
import com.mapbar.ure.utils.TwoKeysHashMap;

/**
 * 使用子集构造法实现NFA到DFA的转化。
 * 
 * @author QIN Jian
 * 
 * @param <T>
 */
public class NFA2DFAConverter<T> {
	public ChangingMonitorHashSet<NFANode<T>> eClosure(
			ChangingMonitorHashSet<NFANode<T>> set) {
		for (NFANode<T> n : set.items()) {
			n.eClosure(set);
		}
		return set;
	}

	public ChangingMonitorHashSet<NFANode<T>> delta(
			ChangingMonitorHashSet<NFANode<T>> set, T c) {
		ChangingMonitorHashSet<NFANode<T>> ret = new ChangingMonitorHashSet<NFANode<T>>();
		for (NFANode<T> n : set.items()) {
			if (n.getNext().containsKey(c)) {
				ret.addAll(n.getNext().get(c));
			}
		}
		return ret;
	}

	public DFA<T> subsetConstruction(HashSet<T> alphabet, NFA<T> nfa) {
		DFA<T> ret = new DFA<T>();
		ArrayList<DFANode<T>> dfas = new ArrayList<DFANode<T>>();
		// init
		ChangingMonitorHashSet<NFANode<T>> q0 = new ChangingMonitorHashSet<NFANode<T>>();
		q0.add(nfa.getStart());
		q0 = eClosure(q0);
		ArrayList<ChangingMonitorHashSet<NFANode<T>>> Q = new ArrayList<ChangingMonitorHashSet<NFANode<T>>>();
		Q.add(q0);
		Stack<ChangingMonitorHashSet<NFANode<T>>> workList = new Stack<ChangingMonitorHashSet<NFANode<T>>>();
		workList.push(q0);

		TwoKeysHashMap<Integer, T, Integer> transitions = new TwoKeysHashMap<Integer, T, Integer>();
		while (!workList.empty()) {
			ChangingMonitorHashSet<NFANode<T>> q = workList.pop();
			for (T c : alphabet) {
				ChangingMonitorHashSet<NFANode<T>> t = eClosure(delta(q, c));
				if (t.items().size() == 0) {
					continue;
				}
				if (Q.indexOf(t) == -1) {
					Q.add(t);
					workList.push(t);
				}

				int idxOfQ = Q.indexOf(q);
				int idxOfT = Q.indexOf(t);
				transitions.put(idxOfQ, c, idxOfT);
			}
		}
		for (int i = 0; i < Q.size(); ++i) {
			dfas.add(new DFANode<T>());
		}
		for (Integer k : transitions.firstKeys()) {
			DFANode<T> dfa = dfas.get(k);
			if (Q.get(k).items().contains(nfa.getEnd())) {
				dfa.setEndState(true);
			}
			Map<T, Integer> subLevel = transitions.get(k);
			for (T k1 : subLevel.keySet()) {
				Integer v = subLevel.get(k1);
				DFANode<T> child = dfas.get(v);
				if (Q.get(v).items().contains(nfa.getEnd())) {
					child.setEndState(true);
				}
				dfa.getNext().put(k1, child);
			}
		}
		ret.setRoot(dfas.get(0));
		ret.setAll(dfas);
		return ret;
	}
}
